The present invention is in the field of network communications. More particularly, the present invention relates to methods and arrangements for reducing retransmission from out of order packets.
In one form of network communications, two nodes may set up a connection. The two nodes may communicate beforehand to decide on the parameters for the connection. Once the connection is established, they may maintain status information about the connection. The status information may include data about sockets, sequence numbers of data sent over the connection, and the amount of data that may be contained in a single transmission. Data sent over a network may be divided into small portions called packets. The packets may consist of the data and header information.
Some connections attempt to be reliable, to insure that all packets transmitted by the sender reach the receiver. In these connections, the receiver may send an acknowledgement (ACK) to the transmitter when it receives a packet. In turn, the transmitter may retransmit a packet if it does not receive an ACK for the packet within a certain period of time (a retransmission timeout interval or RTO). Reliable connections may also include some form of error checking.
Transmission Control Protocol (TCP) is a standard transport-level protocol that utilizes reliable connections. Many application protocols use TCP, including SMTP (simple mail transfer protocol); HTTP, used for the web; POP3, for email retrieval; Telnet, and FTP. TCP may provide a data stream transfer between two processes. Bytes of data are divided into packets called segments. The bytes are numbered sequentially. An ACK for a segment references the sequence number of the next byte of data not yet delivered. For example, if a node receives a segment containing bytes 0 through 49, it would transmit an ACK referring to byte 50. If the receiver receives segments out of order, it continues to send ACKs referring to a missing segment. In the previous example, if the receiver then received a segment with bytes 100 through 149, it would respond with another ACK referring to byte 50, because the segment containing that byte had still not arrived. Under the protocol, a sender may not be sure exactly what packets have been received. If the sender had also sent out a segment with bytes 150 through 199, the sender may not be able to determine whether the receiver had received the segment with bytes 100 through 149 or the segment with bytes 150 through 199.
TCP implementations may provide a variety of algorithms for determining an RTO. In one version, the RTO may be based upon an estimated time for a round trip journey (RTT) of a segment from the sender to the receiver and an ACK back to the sender. The transmitter may estimate the RTT by measuring the time from sending a segment to the time of receiving an acknowledgement. In one version, a TCP implementation maintains an estimated RTT, EstimatedRTT, and continually updates it with a current or SampleRTT. Each time the implementation sends a data segment and receives an ACK, it measures the difference in time as the SampleRTT. It then updates the EstimatedRTT by the iterative formula:EstimatedRTT=α×EstimatedRTT+(1−α)×SampleRTT. α is a parameter to weight the contributors to the updated value. In many implementations, α is a value between 0.8 and 0.9. Given EstimatedRTT, RTO is calculated by:RTO=2×EstimatedRTT 
Another algorithm is similar, but reacts to timeouts more conservatively. Each time there is a timeout, the new RTO is set to twice the previous one:RTO=2×RTO. 
In yet another version, the setting of the RTO after a timeout depends upon the variance of the round trip times. If the variance is small, the change in value of the RTO may be small. If the variance is large, however, the change in value of the RTO may be larger. This algorithm is as follows:Difference=SampleRTT−EstimatedRTT EstimatedRTT=EstimatedRTT+(δ×Difference)Deviation=Deviation+δ(|Difference|−Deviation)RTO=μ×EstimatedRTT+φ×DeviationHere, δ is value between 0 and 1, μ may be set to 1 and φ is often set to 4. When the variance is small, the new value of RTO may be approximately equal to the old value. When the variance is large, the value of the second summand of the last equation may dominate.
Some TCP implementations may retransmit a segment even before the RTO for the segment has expired. In the fast retransmit procedure, the implementation may retransmit a segment after receiving duplicate ACKs indicating that the segment is missing. For example, a TCP implementation may send out segments 1 through 4 ending with bytes 49, 99, 149, and 199. It may then receive 3 ACKs referring to byte 50 of segment 2 as the next expected byte. The implementation may determine that the segment 2 was lost, because the two segments sent afterwards arrived. It may then retransmit segment 2 even before expiration of the RTO for segment 2. In many implementations, fast retransmit is executed upon receiving a third duplicate ACK for a segment.